package sort.堆排序;

import java.util.ArrayList;

public class Heap {
    public ArrayList<Node> nodeList;
    // 堆大小
    private int length;
    public Heap() {}
    public Heap(ArrayList<Node> nodeList) {
        this.nodeList = nodeList;
        this.length = nodeList.size();
    }
    // 交换函数，交换两个节点的位置
    public void swap(Node nodeA,Node nodeB) {
        Node nodeTemp = new Node(nodeA.key,nodeA.value);
        nodeA.key=nodeB.key;
        nodeA.value=nodeB.value;
        nodeB.key=nodeTemp.key;
        nodeB.value=nodeTemp.value;
    }
    public int length() {
        return length;
    }
    // 判断是不是叶子节点
    public boolean isLeaf(int pos) {
        return (pos >= length / 2) && (pos < length);
    }
    // 返回左孩子节点的位置
    public int leftChild(int pos) {
        return 2*pos + 1;
    }
    // 返回右孩子节点的位置
    public int rightChild(int pos) {
        return 2*pos + 2;
    }
    // 返回父节点的地址
    public int parent(int pos) {
        return (pos - 1) / 2;
    }
    // 建堆函数
    public void buildHeap() {
        for (int i = length / 2 -1; i >= 0 ; i--) {
            // 从倒数第二层开始向上逐层遍历
            shiftDown(i);
        }
    }
    // 下拉函数
    public void shiftDown(int pos) {
        while(!isLeaf(pos)){//到叶结点就停止
            int j = leftChild(pos);
            int r = rightChild(pos);
            // j用来标记最大值的位置
            if((r<length)&&(nodeList.get(r).key>nodeList.get(j).key))
            {j=r;}
            if(nodeList.get(pos).key>nodeList.get(j).key) {return;}
            //如果根节点的值小于较大子节点的值就交换位置
            swap(nodeList.get(pos),nodeList.get(j));
            //继续往原来值较大的节点走
            pos = j;
        }
    }
    //插入新节点
    public void insert(Node node){
        nodeList.add(node);
        int curr=nodeList.size()-1;//将新节点放在最后
        //加入以后开始上拉
        while((curr!=0)&&(nodeList.get(curr).key>nodeList.get(parent(curr)).key)){
            swap(nodeList.get(curr),nodeList.get(parent(curr)));
            curr=parent(curr);
        }
        length++;
    }
    //取最大值函数
    public Node removeFirst(){
        if(length<=0){
            System.out.println("Heap is empty");
            return null;
        }
        swap(nodeList.get(0),nodeList.get(--length));//和最后一个位置交换
        if(length!=0) shiftDown(0);
        return nodeList.get(length);//返回最大值
    }
    public static void main(String[] args) {
        ArrayList<Node>nodeList=new ArrayList<Node>();
        nodeList.add(new Node(1,"A"));
        nodeList.add(new Node(5,"E"));
        nodeList.add(new Node(3,"C"));
        nodeList.add(new Node(2,"B"));
        nodeList.add(new Node(4,"D"));
        nodeList.add(new Node(13,"M"));
        nodeList.add(new Node(7,"G"));
        nodeList.add(new Node(6,"F"));
        nodeList.add(new Node(8,"H"));
        nodeList.add(new Node(9,"I"));
        nodeList.add(new Node(10,"J"));




        Heap heap=new Heap(nodeList);

        System.out.println("当前的数组结构");
        for(int i=0;i<heap.length();i++){
            System.out.println(heap.nodeList.get(i).key+"-"+heap.nodeList.get(i).value);
        }

        heap.buildHeap();
        System.out.println("当前的堆结构");
        for(int i=0;i<heap.length();i++){
            System.out.println(heap.nodeList.get(i).key+"-"+heap.nodeList.get(i).value);
        }
        Node result=heap.removeFirst();
        System.out.println("最大值:"+result.key+result.value);
        result=heap.removeFirst();
    }

}